package com.zlk.algorithm.algorithm.sort.heap;

import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @ClassName SortArrayDistanceLessK
 * @description:已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k
 * k相对于数组长度来说是比较小的。请选择一个合适的排序策略，对这个数组进行排序。
 * @author: slfang
 * @create: 2024-01-23 14:35
 * @Version 1.0
 **/
public class SortArrayDistanceLessK {

    @Test
    public void test1(){

//        int[] arr = new int[]{1,20,4,8,22,4};
//        //输出 1  取整
//        System.out.println(arr[-1/2]);
        int testTimes = 1000;
        int maxVal = 100;
        int maxLen = 20;
        for (int i = 0; i < testTimes; i++) {
            int k = (int) (Math.random() * maxLen) + 1;
            int[] randomArr = randomArrayNoMoveMoreK(maxVal, maxLen,k);
            int[] copyArr = Arrays.copyOf(randomArr, randomArr.length);
            int[] org = Arrays.copyOf(randomArr, randomArr.length);
            Arrays.sort(randomArr);
            sortArrayDistanceLessK(copyArr,k);
            if(!SortUtils.isEqual(randomArr,copyArr)){
                System.out.println("fail");
                System.out.println("org:"+Arrays.toString(org));
                System.out.println("random:"+Arrays.toString(randomArr));
                System.out.println("copyArr:"+Arrays.toString(copyArr));
                return ;
            }
        }
        System.out.println("success!");
    }

    public int[] randomArrayNoMoveMoreK(int maxSize, int maxValue, int K) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        // 先排个序
        Arrays.sort(arr);
        // 然后开始随意交换，但是保证每个数距离不超过K
        // swap[i] == true, 表示i位置已经参与过交换
        // swap[i] == false, 表示i位置没有参与过交换
        boolean[] isSwap = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int j = Math.min(i + (int) (Math.random() * (K + 1)), arr.length - 1);
            if (!isSwap[i] && !isSwap[j]) {
                isSwap[i] = true;
                isSwap[j] = true;
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        return arr;
    }

    // 1 2 3    4 5 0    2
    public void sortArrayDistanceLessK(int[] arr,int k){
        if(k==0||arr.length<2||arr==null){
            return ;
        }
        if(k>arr.length){//控制好边界
            k = arr.length;
        }
        PriorityQueue<Integer> priorityQueue =new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            priorityQueue.add(arr[i]);
        }
        int index = 0;
        for (int i = k; i <arr.length ; i++) {
            priorityQueue.add(arr[i]);
            arr[index++] =priorityQueue.poll();
        }
        while (!priorityQueue.isEmpty()){
            arr[index++] = priorityQueue.poll();
        }
    }


}
